{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Fair Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestFair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最近的公平整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>正整数</strong>&nbsp;<code>n</code>。</p>\n",
    "\n",
    "<p>如果一个整数 <code>k</code> 中的&nbsp;<strong>偶数&nbsp;</strong>位数与<strong> 奇数</strong> 位数相等，那么我们称&nbsp;<code>k</code> 为公平整数。</p>\n",
    "\n",
    "<p>返回&nbsp;<em><strong>大于或等于&nbsp;</strong></em><code>n</code><em> 的&nbsp;<strong>最小&nbsp;</strong>的公平整数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2\n",
    "<strong>输出:</strong> 10\n",
    "<strong>解释:</strong> 大于等于 2 的最小的公平整数是 10。\n",
    "10是公平整数，因为它的偶数和奇数个数相等 (一个奇数和一个偶数)。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 403\n",
    "<strong>输出:</strong> 1001\n",
    "<strong>解释:</strong> 大于或等于 403 的最小的公平整数是 1001。\n",
    "1001 是公平整数，因为它有相等数量的偶数和奇数 (两个奇数和两个偶数)。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-fair-integer](https://leetcode.cn/problems/closest-fair-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-fair-integer](https://leetcode.cn/problems/closest-fair-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '403']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestFair(self, num: int) -> int:\n",
    "        while True:\n",
    "            if sum(1 if int(char) & 1 else -1 for char in str(num)) == 0:\n",
    "                return num\n",
    "            num += 1\n",
    "            len_ = len(str(num))\n",
    "            if len_ & 1:  # !num的位数为奇数时，直接变为最近的偶数位数的数\n",
    "                num = 10**len_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestFair(self, n: int) -> int:\n",
    "        l  = len(str(n))\n",
    "        \n",
    "        # 如果位数是奇数，直接构造 l+1 位里最小的公平整数\n",
    "        if l % 2:\n",
    "            return int('1' + '0' * ((l + 1) // 2) + '1' * (l // 2))\n",
    "        \n",
    "        # 验证给定整数是否满足题意（即是否是公平整数）\n",
    "        def check(k):\n",
    "            even, odd = 0, 0\n",
    "            while k:\n",
    "                cur = k % 10\n",
    "                if cur % 2:\n",
    "                    odd += 1\n",
    "                else:\n",
    "                    even += 1\n",
    "                k //= 10\n",
    "            return even == odd\n",
    "        \n",
    "        # 这个循环看似可能会超时，实则不会，因为有效的答案一定会在循环内找到\n",
    "        for j in range(n, 10 ** l):\n",
    "            if check(j):\n",
    "                return j\n",
    "        \n",
    "        # 这说明遇到了前半部分全 9 的坑人情况，这时返回 l+2 位里最小的公平整数\n",
    "        return int('1' + '0' * (l // 2 + 1) + '1' * (l // 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # % 分类讨论\n",
    "    def closestFair(self, n: int) -> int:\n",
    "        l  = len(str(n))\n",
    "        if l % 2:\n",
    "            return int('1' + '0' * ((l + 1) // 2) + '1' * (l // 2)) # 位数是奇数就直接构造l+1位里最小的就可以了\n",
    "        \n",
    "        def check(k): # 验证给定整数是否满足题意\n",
    "            even, odd = 0, 0\n",
    "            while k:\n",
    "                cur = k % 10\n",
    "                if cur % 2:\n",
    "                    odd += 1\n",
    "                else:\n",
    "                    even += 1\n",
    "\n",
    "                k //= 10\n",
    "\n",
    "            return even == odd\n",
    "\n",
    "\n",
    "        for j in range(n, 10 ** l): #这个循环看似超时实则不会\n",
    "            if check(j):\n",
    "                return j\n",
    "\n",
    "        return int('1' + '0' * (l // 2 + 1) + '1' * (l // 2)) # 这说明遇到了前半部分全9的坑人情况，这时返回l+2位里最小的\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestFair(self, n: int) -> int:\n",
    "\n",
    "        l  = len(str(n))\n",
    "        if l % 2:\n",
    "            return int('1' + '0' * ((l + 1) // 2) + '1' * (l // 2)) # 位数是奇数就直接构造l+1位里最小的就可以了\n",
    "        \n",
    "        def check(k): # 验证给定整数是否满足题意\n",
    "            even, odd = 0, 0\n",
    "            while k:\n",
    "                cur = k % 10\n",
    "                if cur % 2:\n",
    "                    odd += 1\n",
    "                else:\n",
    "                    even += 1\n",
    "\n",
    "                k //= 10\n",
    "\n",
    "            return even == odd\n",
    "\n",
    "\n",
    "        for j in range(n, 10 ** l): #这个循环看似超时实则不会\n",
    "            if check(j):\n",
    "                return j\n",
    "\n",
    "        return int('1' + '0' * (l // 2 + 1) + '1' * (l // 2)) # 这说明遇到了前半部分全9的坑人情况，这时返回l+2位里最小的\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestFair(self, n: int) -> int:\n",
    "\n",
    "        l  = len(str(n))\n",
    "        if l%2:\n",
    "            return int('1'+'0'*((l+1)//2)+'1'*(l//2)) # 位数是奇数就直接构造l+1位里最小的就可以了\n",
    "        \n",
    "        def check(k): # 验证给定整数是否满足题意\n",
    "            even,odd = 0,0\n",
    "            while k:\n",
    "                cur = k%10\n",
    "                if cur%2:\n",
    "                    odd+=1\n",
    "                else:\n",
    "                    even+=1\n",
    "                k//=10\n",
    "            return even==odd\n",
    "\n",
    "        for j in range(n,10**l): #这个循环看似超时实则不会\n",
    "            if check(j):\n",
    "                return j\n",
    "        return int('1'+'0'*(l//2+1)+'1'*(l//2)) # 这说明遇到了前半部分全9的坑人情况，这时返回l+2位里最小的\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
